package ljl.alg.wangzheng_camp.round1.stack_and_queue;

import java.util.Deque;
import java.util.LinkedList;

public class _03_05_sorted_stack {
    
    /**
     * 说只能用一个辅助栈，就是可以用两个栈。
     *
     * 栈顶总是最小，说明新元素如果比旧元素大，需要往里挪挪；
     * 旧元素总是有序的，新元素需要找位置
     * 找到第一个比它大的才停止
     *
     * */
    class SortedStack {
        
        Deque<Integer> stack1 = new LinkedList<>();
        Deque<Integer> stack2 = new LinkedList<>();
        public void push(int val) {
            while (!stack1.isEmpty() && stack1.peek() < val)
                stack2.push(stack1.pop());
            stack1.push(val);
            while (!stack2.isEmpty())
                stack1.push(stack2.pop());
        }
        
        public void pop() {
            stack1.pop();
        }
        
        public int peek() {
            return isEmpty() ? -1 : stack1.peek();
        }
        
        public boolean isEmpty() {
            return stack1.isEmpty();
        }
    }
    
    /**
     * 别人的题解
     * */
    class SortedStack2 {
        Deque<Integer> stack = new LinkedList<>();
        Deque<Integer> tmp = new LinkedList<>();
        
        public void push(int val) {
            int max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
            int min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek();
            while(true){
                if(val > max){
                    tmp.push(stack.pop());
                    max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
                }
                else if(val < min){
                    stack.push(tmp.pop());
                    min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek();
                }
                else{
                    stack.push(val);
                    break;
                }
            }
        }
        
        public void pop() {
            //将辅助栈元素push回原始栈
            while (!tmp.isEmpty()){
                stack.push(tmp.pop());
            }
            if (!stack.isEmpty())
                stack.pop();
        }
        
        public int peek() {
            //将辅助栈元素push回原始栈
            while (!tmp.isEmpty()){
                stack.push(tmp.pop());
            }
            return stack.isEmpty() ? -1 : stack.peek();
        }
        
        public boolean isEmpty() {
            return stack.isEmpty() && tmp.isEmpty();
        }
    }
    
    /**
     * 我改的好看了点
     * */
    class SortedStack3 {
        Deque<Integer> stack = new LinkedList<>();
        Deque<Integer> helper = new LinkedList<>();
        public void push(int val) {
            while (!stack.isEmpty() && val > stack.peek())
                helper.push(stack.pop());
            while (!helper.isEmpty() && val < helper.peek())
                stack.push(helper.pop());
            stack.push(val);
        }
        public void pop() {
            peek();
            if (!isEmpty())
                stack.pop();
        }
        public int peek() {
            while (!helper.isEmpty())
                stack.push(helper.pop());
            return isEmpty() ? -1 : stack.peek();
        }
        public boolean isEmpty() {
            return stack.isEmpty() && helper.isEmpty();
        }
    }
    
}
